// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package liveness

import (
	"fmt"

	"cmd/compile/internal/base"
	"cmd/compile/internal/bitvec"
	"cmd/compile/internal/ir"
	"cmd/compile/internal/objw"
	"cmd/compile/internal/ssa"
	"cmd/internal/obj"
	"cmd/internal/objabi"
)

// 参数活跃度跟踪。对于在寄存器中传递的参数，此文件跟踪其溢出槽是否为实时运行时跟踪。参数溢出槽在PC 
// /上是活动的，如果我们知道在这一点或之前已经存储了一个实际值。
// 
// 堆栈参数始终处于活动状态，在此代码中不会被跟踪。堆栈参数是
// 放置在寄存器溢出插槽之前，因此我们发出
// 需要跟踪的最小偏移量。偏移量之前的插槽始终处于活动状态。这个偏移量是
// 通常是第一个溢出槽的偏移量。但如果第一个溢出槽是
// always live（例如，如果它是地址），它将是后面
// 1的偏移量。
// 
// 活性信息作为FUNCDATA和PCDATA发出。
// 
// FUNCDATA格式：
// -需要跟踪的起始（最小）偏移量（1字节）
// -位图列表。
// 如果第i个溢出槽处于活动状态，则在位图中设置位i。
// 
// 在活跃度信息发生变化的PC上，PCDATA指示FUNCDATA中活跃度映射的字节偏移量。PCDATA-1是
// 表示所有插槽都处于活动状态的特殊情况（对于二进制大小
// 保存）。

const allLiveIdx = -1

// 名称和偏移量
type nameOff struct {
	n   *ir.Name
	off int64
}

func (a nameOff) FrameOffset() int64 { return a.n.FrameOffset() + a.off }
func (a nameOff) String() string     { return fmt.Sprintf("%v+%d", a.n, a.off) }

type blockArgEffects struct {
	livein  bitvec.BitVec // 块入口活动的变量
	liveout bitvec.BitVec // 块出口活动的变量
}

type argLiveness struct {
	fn   *ir.Func
	f    *ssa.Func
	args []nameOff         // 溢出槽的名称和偏移量
	idx  map[nameOff]int32 // 参数中的索引

	be []blockArgEffects // 按块ID索引

	bvset bvecSet // 用于唯一化的活动位图集。

	// 在每个值（变化处）和块条目处的活动度映射索引。
	// 在计算过程中，索引临时索引到bvset。
	// 最后，它们将作为输出数据的索引（偏移量）（更改
	// in（*argLiveness）。发射）。
	blockIdx map[ssa.ID]int
	valueIdx map[ssa.ID]int
}

// ArgLiveness计算寄存器参数溢出槽的活跃度信息。
// 如果我们知道某个参数的溢出槽包含有意义的值，则该参数的溢出槽是“活动的”，也就是说，我们已将寄存器值存储到它。
// 返回每个块条目和每个值的活动度映射索引（其中
// 它会更改）。
func ArgLiveness(fn *ir.Func, f *ssa.Func, pp *objw.Progs) (blockIdx, valueIdx map[ssa.ID]int) {
	if f.OwnAux.ABIInfo().InRegistersUsed() == 0 || base.Flag.N != 0 {
		// 没有寄存器参数。没有东西可以散发。
		// 或者如果使用了-N，我们会提前泄漏所有信息，这样它就会一直处于活动状态。
		return nil, nil
	}

	lv := &argLiveness{
		fn:       fn,
		f:        f,
		idx:      make(map[nameOff]int32),
		be:       make([]blockArgEffects, f.NumBlocks()),
		blockIdx: make(map[ssa.ID]int),
		valueIdx: make(map[ssa.ID]int),
	}
	// 收集所有寄存器arg溢出插槽。
	for _, a := range f.OwnAux.ABIInfo().InParams() {
		n, ok := a.Name.(*ir.Name)
		if !ok || len(a.Registers) == 0 {
			continue
		}
		_, offs := a.RegisterTypesAndOffsets()
		for _, off := range offs {
			if n.FrameOffset()+off > 0xff {
				// 我们只打印有限数量的参数，堆栈
				// 偏移量不大于255。
				continue
			}
			lv.args = append(lv.args, nameOff{n, off})
		}
	}
	if len(lv.args) > 10 {
		lv.args = lv.args[:10] // 我们打印的参数不超过10个。
	}

	// 我们预先泄露了地址已被占用或无法使用SSA的值，所以它们始终处于活动状态。
	alwaysLive := func(n *ir.Name) bool { return n.Addrtaken() || !f.Frontend().CanSSA(n.Type()) }

	// 我们将为需要活动度信息的插槽发出最小偏移量。
	// 如果插槽始终处于活动状态，则无需包含偏移量较低的插槽。
	for len(lv.args) > 0 && alwaysLive(lv.args[0].n) {
		lv.args = lv.args[1:]
	}
	if len(lv.args) == 0 {
		return // 一切都是实时的
	}

	for i, a := range lv.args {
		lv.idx[a] = int32(i)
	}

	nargs := int32(len(lv.args))
	bulk := bitvec.NewBulk(nargs, int32(len(f.Blocks)*2))
	for _, b := range f.Blocks {
		be := &lv.be[b.ID]
		be.livein = bulk.Next()
		be.liveout = bulk.Next()

		// 初始化为所有的1，所以我们可以和他们
		be.livein.Not()
		be.liveout.Not()
	}

	entrybe := &lv.be[f.Entry.ID]
	entrybe.livein.Clear()
	for i, a := range lv.args {
		if alwaysLive(a.n) {
			entrybe.livein.Set(int32(i))
		}
	}

	// 以相反的顺序访问块，计算块效果。
	po := f.Postorder()
	for i := len(po) - 1; i >= 0; i-- {
		b := po[i]
		be := &lv.be[b.ID]

		// 如果插槽在所有前置程序中都处于活动状态，则该插槽在块入口处于活动状态。
		for _, pred := range b.Preds {
			pb := pred.Block()
			be.livein.And(be.livein, lv.be[pb.ID].liveout)
		}

		be.liveout.Copy(be.livein)
		for _, v := range b.Values {
			lv.valueEffect(v, be.liveout)
		}
	}

	// 合并相同的活载体。计算每台电脑的活跃度指数
	// 它在哪里变化。
	live := bitvec.New(nargs)
	addToSet := func(bv bitvec.BitVec) (int, bool) {
		if bv.Count() == int(nargs) { // 所有活动的特例
			return allLiveIdx, false
		}
		return lv.bvset.add(bv)
	}
	for _, b := range lv.f.Blocks {
		be := &lv.be[b.ID]
		lv.blockIdx[b.ID], _ = addToSet(be.livein)

		live.Copy(be.livein)
		var lastv *ssa.Value
		for i, v := range b.Values {
			if lv.valueEffect(v, live) {
				// 记录活动度的变化，但现在不发出地图。
				// 对于一系列存储规则，我们最后只需要发出一个
				// 即可。
				lastv = v
			}
			if lastv != nil && (mayFault(v) || i == len(b.Values)-1) {
				// 如果可能发生故障，或在
				// 区块的末尾，则发出活跃度图。如果指令
				// 可能导致恐慌，我们可能需要回溯。
				var added bool
				lv.valueIdx[lastv.ID], added = addToSet(live)
				if added {
					// live已添加到bvset，我们现在无法修改。
					// 复制一份。
					t := live
					live = bitvec.New(nargs)
					live.Copy(t)
				}
				lastv = nil
			}
		}

		// 精神检查。
		if !live.Eq(be.liveout) {
			panic("wrong arg liveness map at block end")
		}
	}

	// Emit funcdata symbol，将索引更新为符号数据中的偏移量。
	lsym := lv.emit()
	fn.LSym.Func().ArgLiveInfo = lsym

	// lv。print（）

	p := pp.Prog(obj.AFUNCDATA)
	p.From.SetConst(objabi.FUNCDATA_ArgLiveInfo)
	p.To.Type = obj.TYPE_MEM
	p.To.Name = obj.NAME_EXTERN
	p.To.Sym = lsym

	return lv.blockIdx, lv.valueIdx
}

// valueEffect将v的效果应用于live，返回是否更改。
func (lv *argLiveness) valueEffect(v *ssa.Value, live bitvec.BitVec) bool {
	if v.Op != ssa.OpStoreReg { // 待办事项：包括其他门店说明吗？
		return false
	}
	n, off := ssa.AutoVar(v)
	if n.Class != ir.PPARAM {
		return false
	}
	i, ok := lv.idx[nameOff{n, off}]
	if !ok || live.Get(i) {
		return false
	}
	live.Set(i)
	return true
}

func mayFault(v *ssa.Value) bool {
	switch v.Op {
	case ssa.OpLoadReg, ssa.OpStoreReg, ssa.OpCopy, ssa.OpPhi,
		ssa.OpVarDef, ssa.OpVarKill, ssa.OpVarLive, ssa.OpKeepAlive,
		ssa.OpSelect0, ssa.OpSelect1, ssa.OpSelectN, ssa.OpMakeResult,
		ssa.OpConvert, ssa.OpInlMark, ssa.OpGetG:
		return false
	}
	if len(v.Args) == 0 {
		return false // 假设常数op不能导致
	}
	return true // 保守地假设所有其他op都可能导致
}

func (lv *argLiveness) print() {
	fmt.Println("argument liveness:", lv.f.Name)
	live := bitvec.New(int32(len(lv.args)))
	for _, b := range lv.f.Blocks {
		be := &lv.be[b.ID]

		fmt.Printf("%v: live in: ", b)
		lv.printLivenessVec(be.livein)
		if idx, ok := lv.blockIdx[b.ID]; ok {
			fmt.Printf("   #%d", idx)
		}
		fmt.Println()

		for _, v := range b.Values {
			if lv.valueEffect(v, live) {
				fmt.Printf("  %v: ", v)
				lv.printLivenessVec(live)
				if idx, ok := lv.valueIdx[v.ID]; ok {
					fmt.Printf("   #%d", idx)
				}
				fmt.Println()
			}
		}

		fmt.Printf("%v: live out: ", b)
		lv.printLivenessVec(be.liveout)
		fmt.Println()
	}
	fmt.Println("liveness maps data:", lv.fn.LSym.Func().ArgLiveInfo.P)
}

func (lv *argLiveness) printLivenessVec(bv bitvec.BitVec) {
	for i, a := range lv.args {
		if bv.Get(int32(i)) {
			fmt.Printf("%v ", a)
		}
	}
}

func (lv *argLiveness) emit() *obj.LSym {
	livenessMaps := lv.bvset.extractUnique()

	// 寄存器arg溢出槽的堆栈偏移量
	argOffsets := make([]uint8, len(lv.args))
	for i, a := range lv.args {
		off := a.FrameOffset()
		if off > 0xff {
			panic("offset too large")
		}
		argOffsets[i] = uint8(off)
	}

	idx2off := make([]int, len(livenessMaps))

	lsym := base.Ctxt.Lookup(lv.fn.LSym.Name + ".argliveinfo")
	lsym.Set(obj.AttrContentAddressable, true)

	off := objw.Uint8(lsym, 0, argOffsets[0]) // 需要活动性信息的最小偏移量。
	for idx, live := range livenessMaps {
		idx2off[idx] = off
		off = objw.BitVec(lsym, off, live)
	}

	// 将活性指数更新为偏移量。
	for i, x := range lv.blockIdx {
		if x != allLiveIdx {
			lv.blockIdx[i] = idx2off[x]
		}
	}
	for i, x := range lv.valueIdx {
		if x != allLiveIdx {
			lv.valueIdx[i] = idx2off[x]
		}
	}

	return lsym
}
